package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/4 3:00 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        int stationNum = gas.length;
        int[] delta = new int[stationNum];
        int sum = 0;
        for (int i = 0; i < stationNum; i++) {
            delta[i] = gas[i] - cost[i];
            sum += delta[i];
        }
        if (sum < 0) {
            return -1;
        }
        int stationCount = 0;
        sum = 0;
        for (int i = 0; i < 2*stationNum; i++) {
            sum += delta[i%stationNum];
            if (sum < 0) {
                sum = 0;
                stationCount = 0;
            }else if (sum >= 0) {
                stationCount++;
                if (stationCount == stationNum) {
                    return (i+1)%stationNum;
                }
            }
        }
        return -1;
    }

    // dsf


    public static void main(String[] args) {
        int[] gas = new int[]{1, 2, 3, 4, 5};
        int[] cost = new int[]{3, 4, 5, 1, 2};

        LeetCode0134 leetCode0134 = new LeetCode0134();
        System.out.println(leetCode0134.canCompleteCircuit(gas, cost));


        int[] gas2 = new int[]{5,1,2,3,4};
        int[] cost2 = new int[]{4,4,1,5,1};
        System.out.println(leetCode0134.canCompleteCircuit(gas2, cost2));

        int[] gas3 = new int[]{3,1,1};
        int[] cost3 = new int[]{1,2,2};
        System.out.println(leetCode0134.canCompleteCircuit(gas3, cost3));

    }


}
